﻿namespace Leetcode.N0433;
public class Solution
{
    public int MinMutation(string start, string end, string[] bank)
    {
        if (start == end)
        {
            return 0;
        }

        var queue = new Queue<int>();
        for (int i = 0; i < bank.Length; i++)
        {
            if (this.GetMutation(start, bank[i]) == 1)
            {
                queue.Enqueue(i);
            }
        }

        bool[] visited = new bool[bank.Length];
        var deep = 1;
        while (queue.Count > 0)
        {
            var list = new List<int>();
            while (queue.Count > 0)
            {
                list.Add(queue.Dequeue());
            }
            foreach (var item in list)
            {
                visited[item] = true;
                if (bank[item] == end)
                {
                    return deep;
                }

                for (int i = 0; i < bank.Length; i++)
                {
                    if (visited[i])
                    {
                        continue;
                    }

                    if (this.GetMutation(bank[item], bank[i]) == 1)
                    {
                        queue.Enqueue(i);
                    }
                }
            }

            deep++;
        }

        return -1;
    }

    private int GetMutation(string s1, string s2)
    {
        var count = 0;
        for (int i = 0; i < s1.Length; i++)
        {
            if (s1[i] != s2[i])
            {
                count++;
            }
        }
        return count;
    }
}